package com.yun.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BucketSort {
    public static void sort1(int[] ages) {
        //1.准备桶
        ArrayList<Integer>[] buckets = new ArrayList[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        //2.放入年龄数据
        for (int age : ages) {
            buckets[age / 10].add(age);
        }
        int k = 0;
        for (ArrayList<Integer> bucket : buckets) {
            //3.排序桶内排序
            Collections.sort(bucket);
            //4.把每个桶排序好的内容，依次放入原始数组
            for (Integer v : bucket) {
                ages[k++] = v;
            }
        }
        System.out.println(Arrays.toString(ages));
    }

    public static void sort(int[] a,int range) {
        int max = a[0];
        int min = a[0];
        for (int j : a) {
            if (j > max) {
                max = j;
            }
            if (j < min) {
                min = j;
            }
        }
        //1.准备桶
        ArrayList<Integer>[] buckets = new ArrayList[(max - min)/range + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        //2.放入年龄数据
        for (int age : a) {
            buckets[(age - min)/range].add(age);
        }
        int k = 0;
        for (ArrayList<Integer> bucket : buckets) {
            //3.排序桶内排序
            Collections.sort(bucket);
            System.out.println(bucket);
            //4.把每个桶排序好的内容，依次放入原始数组
            for (Integer v : bucket) {
                a[k++] = v;
            }
        }
        System.out.println(Arrays.toString(a));
    }

    public static void main(String[] args) {
        int[] ages = {20, 18, 28, 66, 25, 31, 67, 30};
        int max = ages[0];
        int min = ages[0];
        for (int j : ages) {
            if (j > max) {
                max = j;
            }
            if (j < min) {
                min = j;
            }
        }
        //1.准备桶
        ArrayList<Integer>[] buckets = new ArrayList[(max - min)/ 3 + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        //2.放入年龄数据
        for (int age : ages) {
            buckets[(age - min)/ 3].add(age);
        }
        int k = 0;
        for (ArrayList<Integer> bucket : buckets) {
            //3.排序桶内排序
            Collections.sort(bucket);
            System.out.println(bucket);
            //4.把每个桶排序好的内容，依次放入原始数组
            for (Integer v : bucket) {
                ages[k++] = v;
            }
        }
        System.out.println(Arrays.toString(ages));
    }
}
